/*
"Min(Max elements rows) not less than Max(Min of columns)"
can you tell me whether above statement ist true or false..
if it true, then tell me solutoin.
if it false, then tell me example

------------------------------------------
                           |      |
------------------------------------------
A                          |   X  |
------------------------------------------
                           |      |
------------------------------------------
                           |      |
------------------------------------------
                           |   B  |
------------------------------------------



X>=B, since B is min of the column
A>=X, since A is max of the row
Therefore, A >=X>=B ==> A>=B
*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int minOfMaxRows(vector<vector<int> > &matrix)
{
    vector<int> num;
    for (int i = 0; i < matrix.size(); i++) {
	sort(matrix[i].begin(), matrix[i].end());
	num.push_back(matrix[i][matrix[0].size()-1]);
    }
    sort(num.begin(), num.end());
    return num[0];
}

void rotate(vector<vector<int> > &matrix1, vector<vector<int> > &matrix)
{
    for (int i = 0; i < matrix.size(); i++) {
	for (int j = 0; j < matrix[0].size(); j++) {
	    matrix1[j][i] = matrix[i][j];
	}
    }
}


int maxOfMinCols(vector<vector<int> > &matrix)
{
    vector<int> num;
    for (int i = 0; i < matrix.size(); i++) {
	sort(matrix[i].begin(), matrix[i].end());
	num.push_back(matrix[i][0]);
    }
    sort(num.begin(), num.end());
    return num[num.size()-1];
}

int main(int argc, char **argv)
{
    /* generate the random matrix */
    vector<vector<int> > matrix(20, vector<int>(30, 0));
    srand ( time(NULL) );

    for (int i = 0; i < 20; i++) {
	for (int j = 0; j < 30; j++) {
	    while(matrix[i][j] == 0) matrix[i][j] = rand()%400;
	    cout << matrix[i][j] << " ";
	}
	cout << endl;
    }
    vector<vector<int> > matrix1(30, vector<int>(20, 0));
    rotate(matrix1, matrix); 
    cout << "Min of Max element of Rows: " << minOfMaxRows(matrix) << endl; 
    cout << "Max of Min element of Cols: " << maxOfMinCols(matrix1) << endl; 
}






